package leetcode.primary;

public class T221 {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length,n = matrix[0].length;
        int[][] dp = new int[m][n];

        int max = 0;
        //dp初始化
        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0]-'0';
            if (dp[i][0]>max){
                max = dp[i][0];
            }
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = matrix[0][j]-'0';
            if (dp[0][j]>max){
                max = dp[0][j];
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j]=='1'){
                    if (matrix[i-1][j-1]>='1'){
                        dp[i][j] = checkout(i,j,dp);
                    }else {
                        dp[i][j] = 1;
                    }
                }else {
                    dp[i][j] = 0;
                }
                if (dp[i][j]>max){
                    max = dp[i][j];
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        return max;

    }

    public int checkout(int i,int j,int[][] dp){
        int v = (int) Math.sqrt(dp[i - 1][j - 1]);

        int x = 1,y = 1;
        for (int k = 1; k <= v; k++) {
            y++;
            if (dp[i-k][j]==0){
                y--;
                break;
            }
        }
        for (int k = 1; k <=v; k++) {
            x++;
            if (dp[i][j-k]==0){
                x--;
                break;
            }
        }

        int len = Math.min(x, y);
        return len*len;
    }

    public static void main(String[] args) {
        T221 t221 = new T221();
        char[][] chars= {
                {'0','0','0','1'},
                {'1','1','0','1'},
                {'1','1','1','1'},
                {'0','1','1','1'},
                {'0','1','1','1'}
        };
        int max = t221.maximalSquare(chars);
        System.out.println(max);
    }
}
/*
* {'1','0','1','0','0'},
*{'1','0','1','1','1'},
*{'1','1','1','1','1'},
*{'1','0','0','1','0'}
*/